Such a storage system, in conjunction with inlets associated with the buffer memory, constitutes a data switching device in which the data received by the inlets is stored in the buffer memory for subsequent forwarding to the outlets, according to selection indications. These selection indications may more generally denote an outgoing destination; they can accompany the data received by the inlets, or be included in this data and will serve to direct its transfer to at least one outlet of a selected outgoing destination. This switching device will be of use in communication networks. But the storage system of the invention, as such, can find many other applications, whenever data structured in data blocks comprising one or more data elements must be made available to multiple outlets belonging to separate destinations. In an expert system, for example, such a storage system can serve to store data to be processed and to submit this data to multiple processors. Several processors accomplishing a particular process in parallel will then be equivalent to an outgoing destination.
In a known embodiment, described in Applicant's commonly assigned U.S. patent application entitled COMMUNICATION SWITCHING ELEMENT AND METHOD FOR TRANSMITTING VARIABLE LENGTH CELLS filed on Aug. 9, 1990 under Ser. No. 565,310 and corresponding to International application. The storage system comprises one queue for each outlet. The function of the queue management logic (or system) is to add the identity of each data block (or cell) stored in the buffer memory, when it is to be transferred to an outgoing destination, to a queue of a selected outlet belonging to a destination, the process being repeated for one or more selected destinations. One outlet of those which belong to a particular outgoing direction is selected for example at random.
The advantage of such a solution lies in its apparent simplicity. When an outlet becomes available it simply serves its own outlet queue which transfers to it the identity of a data block in the buffer memory which is addressed to it.
However, each outlet must deal with the transfers for which it is asked by its queue, that is which have previously been assigned to it, without regard for its present situation which may be unfavorable with respect to such traffic (overload, failure, under maintenance, etc). In addition, queue entry takes no account of the traffic load already assigned to an outlet nor does it take into account, in this traffic load, of the different lengths of the data blocks assigned to it. It follows that this solution inherently places an unequal load on the different outlets belonging to a particular outgoing destination.
To overcome this disadvantage, different known solutions consist in adding, for each outlet, a device for measuring the cumulative queuing time relative to this outlet or, in other words, the accumulated quantity of information waiting for this outlet, that is the total number of data elements representing the queued variable length data blocks. Then the traffic is spread equally over the outlets by a circuit for selecting the outlet out of a group of outlets, the cumulative queuing time measuring circuit of which indicates a value lower than those of the other outlets of this group.
In addition, it is often necessary for the choice of outlet from a group of outlets to introduce a decorrelation to the outgoing traffic (that is for the choice to be made without regard to the previous flow of traffic over the outlets). Taken in isolation, this requirement is simple to satisfy, by introducing the effect of a source of random signals in the choice of one of the outlets of the group. However, the use of this arrangement becomes more expensive or slower in the case of a point-to-multipoint cell transfer; in such a case, the identity of the cell must be written in a number of queues, one for each outlet selected to receive a copy of the cell addressed to one of the several selected destination outlet groups. In this case a random selection circuit is required for each group of outlets, to proceed in parallel and without additional delay, or else it is necessary to proceed serially in time for the different groups of selected outlets, which increases execution time.
The problem becomes much more complicated when the two preceding requirements (distributing the traffic equally over the different outlets in each group and random choice of outlets to decorrelate outgoing traffic) must be satisfied simultaneously. The basic algorithms described previously for these two requirements considered in isolation are contradictory. They cannot be logically combined in a simple way to satisfy these requirements at the actual moment of outgoing transfer of the data blocks to the selected outlets (reading of the queues), whereas the selection operation is performed when the identity of the data block is written in one (or more) outlet queues. The implementation of a solution combining the algorithms required to satisfy these two requirements, including the case of point-to-multipoint transfer, by selecting an outlet in each group of destination outlets, before writing the identity of the data block in the outlet queue involves very considerable complexity and is therefore very expensive.